﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data;

namespace ID3_Algorithm.Tree
{
    public class DecisionTree
    {
        private TreeNode root;

        //Algorithm variables - BEGIN
        DataTable dt;
        List<Attribute> attributes;
        private string positiveLabel = "YES";
        private string negativeLabel = "NO";
        private string conceptColumn;
        // END

         //public DecisionTree(DataTable dt_, List<Attribute> attributes)
        public DecisionTree()
        {
        //    this.dt = dt_;
        //    this.attributes = attributes;
            this.root = null;
        }

        public TreeNode Root 
        {
            get { return this.root; }
            set { this.root = value; } 
        }

        // Algorithm logic from now on

        /// <summary>
        /// Property method for concept column name 
        /// </summary>
        public string ConceptColumn
        {
            get { return this.conceptColumn; }
            set { this.conceptColumn = value; }
        }

        /// <summary>
        /// This method forms decison tree of ID3 algorithm by some form of recursion. It is not real recursion as iterative calls are done on a new instance of a tree node every time the method is called.
        /// </summary>
        /// <returns>TreeNode<T></returns>
        public TreeNode FormId3DecisionTree(DataTable dt_, List<Attribute> attributes)
        {
              TreeNode tn = new TreeNode();
              if (AllInstancesPositive(dt_) == true)
              {
                  tn.Value = "YES";
                  return tn;
              }
              if (AllInstancesNegative(dt_) == true)
              {
                  tn.Value = "NO";
                  return tn;
              }
              if (attributes.Count == 0)
              {
                  tn.Value = ReturnMostCommonValueFromInstances(dt_);
                  return tn;
              }
              Attribute selectedAttribute = SelectBestAttribute(attributes, dt_);
              tn.Value = selectedAttribute;
              tn.Children = selectedAttribute.Values.Count;

              for (int i = 0; i < selectedAttribute.Values.Count; i++)
              {
                  DataTable dtSubset = ReturnInstancesWithSpecificValue(selectedAttribute, dt_, selectedAttribute.Values[i]);
                  if (dtSubset.Rows.Count != 0)
                  {
                      attributes.Remove(selectedAttribute);
                      tn[i] = FormId3DecisionTree(dtSubset, attributes);
                  }
                  else { tn.RemoveSpecifiedChild(tn[i]); }
              }
              return tn; 
        }


        /// <summary>
        /// Method searches for concept column value which has the most occurances.
        /// </summary>
        /// <param name="dt_"></param>
        /// <returns>string</returns>
        private string ReturnMostCommonValueFromInstances(DataTable dt_)
        {
            int nrOfPositiveInstances = 0;
            int nrOfNegativeInstances = 0;

            foreach (DataRow row in dt_.Rows)
            {
                if (row[ConceptColumn].ToString().Equals(positiveLabel))
                    nrOfPositiveInstances++;
                if (row[ConceptColumn].ToString().Equals(negativeLabel))
                    nrOfNegativeInstances++;
            }

            return nrOfNegativeInstances > nrOfPositiveInstances ? "NO" : "YES";
        }

        /// <summary>
        /// Method returns all instances that have attribute value specified by input argument
        /// </summary>
        /// <param name="attValue">string</param>
        /// <returns>DataTable</returns>
        private DataTable ReturnInstancesWithSpecificValue(Attribute at, DataTable dt_, string attValue)
        {
            DataTable dtSubset = new DataTable();
            dtSubset = dt_.Clone();

            foreach (DataRow row in dt_.Rows)
            {
                if (row[at.Name].ToString() == attValue)
                {
                    dtSubset.ImportRow(row);
                }
            }

            return dtSubset;
        }

        /// <summary>
        /// This method checks to see if all instances in datatable are negative. This is used when classifying a node as a leaf
        /// </summary>
        /// <returns>bool</returns>
        private bool AllInstancesNegative(DataTable dt_)
        {
            bool allInstancesPositive = true;
            foreach (DataRow row in dt_.Rows)
            {
                if (row[ConceptColumn].ToString() == positiveLabel)
                {
                    allInstancesPositive = false;
                    break;
                }
            }
            return allInstancesPositive;
        }

        /// <summary>
        /// This method is used to check whetere or not all instances in a datatable belong to positive concept. This helps in further clasifying of a node as a leaf
        /// </summary>
        /// <returns>bool</returns>
        private bool AllInstancesPositive(DataTable dt_)
        {
            bool allInstancesPositive = true;
            foreach (DataRow row in dt_.Rows)
            {
                if (row[ConceptColumn].ToString() == negativeLabel)
                {
                    allInstancesPositive = false;
                    break;
                }
            }
            return allInstancesPositive;
        }

        /// <summary>
        /// Method checks if all instances of a datatable are of the same concept class, whether positive or negative.
        /// </summary>
        /// <returns></returns>
        public bool AllInstancesBelongToTheSameConceptClass(DataTable dt_)
        {
            string conceptColumnTrue = string.Format("{0} = '{1}'", ConceptColumn, positiveLabel);
            DataRow[] rowsTrue = dt_.Select(conceptColumnTrue);

            string conceptColumnFalse = string.Format("{0} = '{1}'", ConceptColumn, negativeLabel);
            DataRow[] rowsFalse = dt_.Select(conceptColumnFalse);

            if (rowsTrue.Length == dt_.Rows.Count)
            {
                return true;
            }
            if (rowsFalse.Length == dt_.Rows.Count)
            {
                return true;
            }

            return false;
        }

        /// <summary>
        /// Method selects the best attribute by using InformationGain measure
        /// </summary>
        /// <returns>Attribute</returns>
        public Attribute SelectBestAttribute(List<Attribute> allAtt, DataTable dt_ )
        {
            Dictionary<string, double> attGainDictionary = new Dictionary<string, double>();
            double gainPerAtt = 0.0;
            foreach (Attribute att in allAtt)
            {
                gainPerAtt = CalculateGainPerAttribute(att,dt_);
                attGainDictionary.Add(att.Name, gainPerAtt);
            }
            
            return allAtt.FirstOrDefault(g => g.Name.Equals(ReturnAttributeWithHighestGain(attGainDictionary)));    
        }

        /// <summary>
        /// Method returns attribute with highest gain value. This method is called from SelectBestAttribute
        /// </summary>
        /// <param name="treeNodeDictionary"></param>
        /// <returns>string</returns>
        private string ReturnAttributeWithHighestGain(Dictionary<string, double> treeNodeDictionary)
        {
            double tempHighestGain = 0.0;
            foreach (var item in treeNodeDictionary)
            {
                if (item.Value > tempHighestGain)
                {
                    tempHighestGain = item.Value;
                }
            }

            return treeNodeDictionary.FirstOrDefault(g => g.Value == tempHighestGain).Key;
        }

        /// <summary>
        /// Method calculates the gain per inputed attribute. Also called only from SelectBestAttribute method
        /// </summary>
        /// <param name="att"></param>
        /// <returns></returns>
        public double CalculateGainPerAttribute(Attribute att,DataTable dt_)
        {
            double informationGainPerAttribute = CalculateEntropy(dt_);
            string[] columnsToQuery = new string[] { att.Name, ConceptColumn };
            DataView dv = new DataView(dt_);
            DataTable dtAtt = dv.ToTable(false, columnsToQuery);
            List<int> flags = new List<int>();

            for (int i = 0; i < att.Values.Count * 2; i++)
            {
                flags.Add(0);
            }

            foreach (DataRow row in dtAtt.Rows)
            {
                for (int i = 0; i < att.Values.Count; i++)
                {
                    if (row[att.Name].ToString() == att.Values[i] && row[ConceptColumn].ToString() == "YES")
                    {
                        flags[2 * i]++;
                        continue;
                    }
                    if (row[att.Name].ToString() == att.Values[i] && row[ConceptColumn].ToString() == "NO")
                    {
                        flags[2 * i + 1]++;
                        continue;
                    }
                }
            }

            double tempSumOfGain = 0.0;
            double allFlagsSummed = 0.0;
            foreach (int item in flags)
            {
                allFlagsSummed += item;
            }

            for (int i = 0; i < flags.Count; i = i + 2)
            {
                double attTotalPositiveNegativePerValue = flags[i] + flags[i + 1];
                double firstAddend = xlog2x(flags[i], attTotalPositiveNegativePerValue);
                double secondAddend = xlog2x(flags[i + 1], attTotalPositiveNegativePerValue);
                tempSumOfGain += (attTotalPositiveNegativePerValue / allFlagsSummed) * (firstAddend + secondAddend);
            }

            return informationGainPerAttribute - tempSumOfGain;
        }

        /// <summary>
        /// Method calculates entropy as per formula specified in ID3 algorithm.
        /// </summary>
        /// <returns></returns>
        public double CalculateEntropy(DataTable dt_)
        {
            int nrOfPositiveExamples = 0;
            int nrOfNegativeExamples = 0;

            DataView dv = new DataView(dt_);
            DataTable onlyConceptColumn = dv.ToTable(ConceptColumn);

            foreach (DataRow row in onlyConceptColumn.Rows)
            {
                if (row[ConceptColumn].ToString() == positiveLabel)
                {
                    nrOfPositiveExamples++;
                }
                if (row[ConceptColumn].ToString() == negativeLabel)
                {
                    nrOfNegativeExamples++;
                }
            }

            int nrOfTotalExamples = nrOfNegativeExamples + nrOfPositiveExamples;
            double tempReturn = xlog2x(nrOfPositiveExamples, nrOfTotalExamples) + xlog2x(nrOfNegativeExamples, nrOfTotalExamples);

            return tempReturn;
        }

        /// <summary>
        /// Method calculates xlog2x where x is ratio of x/y form and x is first input parameter while y is second.
        /// </summary>
        /// <param name="numerator"></param>
        /// <param name="denumerator"></param>
        /// <returns></returns>
        private double xlog2x(double numerator, double denumerator)
        {
            double tempSum;
            if (numerator == 0 || denumerator == 0)
            {
                return 0.0;
            }
            else
                tempSum = -numerator / denumerator;
            tempSum *= Math.Log(numerator / denumerator, 2);

            return tempSum;
        }
    }
}
